{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        if(len(board) == 0 or len(board[0]) == 0):\n",
    "            return False\n",
    "        if(len(word) == 0):\n",
    "            return True\n",
    "        rows = len(board)\n",
    "        cols = len(board[0])\n",
    "        ###在board外加一层none,避免每次都要判断是否越界。\n",
    "        for r in range(rows):\n",
    "            board[r] = [None] + board[r] + [None]\n",
    "        cols += 2\n",
    "        rows += 2\n",
    "        board = [[None] * cols] + board + [[None] * cols]\n",
    "        #####\n",
    "        n = len(word)\n",
    "        def Find(idx,r,c) -> bool:\n",
    "            if(idx >= n or board[r][c] != word[idx]):\n",
    "                return False\n",
    "            if(idx == n - 1):\n",
    "                return True\n",
    "            temp = board[r][c]\n",
    "            board[r][c] = None #防止重复访问\n",
    "            idx += 1\n",
    "            result = Find(idx, r+1, c) or Find(idx, r-1, c) or Find(idx, r, c-1) or Find(idx, r, c+1)\n",
    "            board[r][c] = temp\n",
    "            return result\n",
    "        for r in range(1, rows):\n",
    "            for c in range(1, cols):\n",
    "                if(Find(0,r,c) == True):\n",
    "                    return True\n",
    "        return False\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('A', 'S', 'A') ('B', 'F', 'D') ('C', 'C', 'E') ('E', 'S', 'E')\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "board =[\n",
    "  ['A','B','C','E'],\n",
    "  ['S','F','C','S'],\n",
    "  ['A','D','E','E']\n",
    "]\n",
    "print(*zip(*board))\n",
    "word = 'SFDEESECBA'\n",
    "word = ''\n",
    "board = [[\"C\",\"A\",\"A\"],\n",
    "         [\"A\",\"A\",\"A\"],\n",
    "         [\"B\",\"C\",\"D\"]]\n",
    "#word = 'AABCDAAAC'\n",
    "a = Solution()\n",
    "print(a.exist(board, word))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
